package main

import "fmt"

/*
约瑟夫环/圆圈中最后剩下的数字
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字
（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：
输入: n = 5, m = 3
输出: 3

示例 2：
输入: n = 10, m = 17
输出: 2
*/

type Child struct {
	next *Child
	val  int
}

/*
解题思路
先模拟熟悉的思路。比如最容易想的链表模拟这个操作过程。随着n的减小，每次新的起点走m次。复杂度为O(n*m)O(n∗m)
数学的思路
f（n, m) 可以表示为最后剩下的数字的下标
考虑如何把f(n, m) 映射到 f(n-1,m)，就是考虑如何把旧序列的编号映射为新序列的编号
()表示删除的元素

0,1,2,(3),4,5 	f(6,3)
4,5 0,(1),2   	f(5,3)
4,5,0,(2)     	f(4,3)
(4),5,0       	f(3,3)
(5),0        	f(2,3)
0            	f(1,3)

可以抽象为startpos + offset = Len。
startpos 表示在新的序列中起始元素的下标。offset = m
Len % n 表示长度为n的串要删除的元素下标。取模操作把散乱的下标映射为[0, n-1]。刚好是我们需要的操作。我感觉大部分人应该是这里的取模运算没搞明白。这样就完成了旧序列到新序列的下标映射。
而重新拼接后，新的元素占据了删除的元素的位置，看上面那个例子（记住是一个环形的表示）。上一步我们求出了删除的元素下标，此时新的元素占据删除的下标，则新的startpos = Len % n。n的长度减一。
可得
f(n, m) = (f(n-1, m)+m)%n
但是这里f(6)的结果我们没法一开始就知道。我们仅知道边界的情况f(1) = 0。表示一个元素时的下标为0。这就是一个很典型的递归程序了。

*/
func lastRemaining(n int, m int) int {
	var ans int
	for i := 2; i <= n; i++ {
		ans = (ans + m) % i
	}
	return ans
}

func main() {
	fmt.Println(lastRemaining(5, 3))
}
